﻿//矩阵中的最长递增路径(hard): https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
class Solution {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int memo[210][210];
    int m,n;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m=matrix.size(),n=matrix[0].size();
        int Max=1;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                Max=max(Max,dfs(i,j,matrix));
            }
        }
        return Max;
    }
    int dfs(int i,int j,vector<vector<int>>& matrix)
    {
        if(memo[i][j])
        {
            return memo[i][j];
        }
        int Max=1;
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k];  int y=j+dy[k];
            if( x>=0&&x<m&&y>=0&&y<n && matrix[x][y]>matrix[i][j])
            {
                Max=max(Max,1+dfs(x,y,matrix));
            }
        }
        memo[i][j]=Max;
        return Max;
    }
};